#include <vector>

struct Point2D
{
	double x;
	double y;
	int id;
};

class KDtree
{
	public:
		KDtree(const std::vector<Point2D>& i_vector);
	private:
		struct Node
		{
			bool m_ifasix_x;
			double value;
			Node * left;
			Node * right;
			Point2D mp_point;
		};
		Node * mp_root;
	private:	
		void p_CreateTree(Node* i_node, std::vector<Point2D>& i_first, 
			std::vector<Point2D>& i_second, int i_lb, int i_rb, int i_count);
};